1. Field of the Invention
The present invention relates to a technique for obtaining an optimum solution or promising solutions to a problem according to a learning algorithm such as an evolutionary algorithm (EA), etc.
2. Description of the Related Art
Currently, the evolutionary algorithm, which is one of the learning algorithms, is applied to a variety of fields such as an LSI arrangement, image processing, scheduling, database classification, etc.
The evolutionary algorithm is a general term for problem-solving algorithms which use the evolution of living things as a model. The mechanism of a typical evolutionary algorithm is that a candidate of a solution to a given problem is recognized as an individual, and the whole of a population composed of individuals is evolved with the steps such as selection, crossover, etc., that is, the population is made to approach an optimum solution (or a semi-optimum solution or a feasible solution).
For example, a genetic algorithm (GA), which is most typical of the evolutionary algorithm, converts a group of solution candidates to a given problem into character strings each of which is recognized as a chromosome, defines a fitness function as a degree of suitability to a solution (that is, a chromosome), and performs the operations for changing a character string, which are recognized as the genetic operations such as selection according to the fitness, crossover, mutation, etc. A series of these genetic operations is regarded as a single generation and several generations are made to elapse so that an entire chromosome population approaches a better solution. A number of chromosomes with higher degrees of fitness emerge from the chromosome population by repeating the series of genetic operation steps for many generations. Consequently, an optimum solution or a semi-optimum solution can be obtained. "Genetic Algorithm" edited by Hiroaki KITANO (Sangyo Tosho ISBN 4-7828-5136-7) and "Genetic Algorithms in Search, Optimization and Machine Learning" edited by David E. Goldberg (Addison-Wesley Pub Co.; ISBN 0-201-15767-5) refer to the evolutionary algorithm and the genetic algorithm in detail.
The evolutionary algorithm can be applied to many types of problems. This algorithm has a characteristic that an optimum solution, a semi-optimum solution, or a feasible solution can be obtained to a large-scale and complicated problem, which is difficult to be solved with conventional methods.
In the evolutionary algorithm, there is a group of parameters (execution conditions) to be set for each given problem when the algorithm is executed, in order to improve its performance. By way of example, there are parameters such as a chromosome representation method, a fitness function, a selection method, a crossover method, a mutation method, etc. in a standard genetic algorithm.
A combination of execution conditions for obtaining the highest performance depends on the type, the scale, etc. of a problem, and its coordination is normally made according to a user's experience and the repetition of algorithm execution. It is said to be desirable that the behavior of the genetic algorithm is grasped in order to coordinate the execution conditions of the evolutionary algorithm and to improve its performance. However, it is not easy to handle the representations of a spatial distribution and a charge with time, namely, the evolution of a population, which is the characteristic of the evolutionary algorithm.
Conventionally, visualization was frequently used as a method for representing the behavior (and the performance) of an evolutionary algorithm. For example, the solution representation of each individual or the degree of suitability (the degree of fitness) of a solution in the evolutionary algorithm is plotted in a solution space or on a time axis by visualizing the behavior of the evolutionary algorithm, so that the behavior can be intuitively represented and displayed even if the execution of the evolutionary algorithm requires a relatively large-scale problem area, a large population, or a large amount of time.
A variety of methods for visualizing the evolutionary algorithm have been developed up to now. For example, the Japanese Laid-Open Patent Gazette No. 9-305565 "Genetic Algorithm Analysis and Display Processing Device" reciting the invention filed by the present applicant discloses the technique intended not only to implement a display visualized by various methods for the genetic algorithm, but to integrate the input and storage of execution conditions and the execution of a genetic algorithm, so that a user can efficiently coordinate the execution conditions and the performance is improved.
However, if the scale of a problem or of the evolutionary algorithm itself (the size of a population, the number of generations, etc.) is significantly large, a computer having the capability for performing high-speed arithmetic operations, and a sufficient disk capacity for storing the detailed record of the evolution of the evolutionary algorithm depending on need, is required. However, such a computer does not always comprise a desired graphics capability for visualizing the behavior of the evolutionary algorithm in a current situation. Therefore, it may sometimes be difficult to process both the execution and the visualized display of the evolutionary algorithm by using a single computer.
Additionally, with the conventional techniques, the visualized display capability does not greatly contribute to the improvement of the performance of the evolutionary algorithm. For example, the conventional techniques do not implement the capability for immediately changing an execution condition while viewing a visualized display, although the progress state of the execution of the evolutionary algorithm is visualized and displayed.